package exercise;

/**
 * @author noob
 * @version 1.0
 * @date 2021/3/17 6:47
 * 插入排序：双重循环，找到合适的位置，替换
 *
 */
public class InsertionSort {

    public static <E extends Comparable<E>>  void sort(E[] arr ){
        for (int i = 0; i < arr.length; i++) {
            E t = arr[i];
            int j;
            for ( j = i; j -1 >= 0 && t.compareTo(arr[j-1]) < 0 ; j--) {
                arr[j]=arr[j-1];
            }

            arr[j] = t;
        }
    }

    public static void main(String[] args) {
        Integer[] arr={4,6,5,2,3,8,7,1};
        InsertionSort.sort(arr);
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i]+ " ");
        }
        System.out.println();
    }
}
